package Hot_100;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

//柱状图中的最大矩形
public class Hot_100_84 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //初始化数组
        int n = sc.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        //调用处理函数并输出结果
        System.out.println(largestRectangleArea(arr));
    }

    /**
     * 求最大矩阵函数
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        int n = heights.length;
        //存左边元素
        int left[] = new int[n];
        //存右边元素
        int right[] = new int[n];
        //单调栈
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            //从左往右构造单调栈
            while (!q.isEmpty() && heights[q.peek()] >= heights[i]) {
                q.pop();
            }
            left[i] = q.isEmpty() ? -1 : q.peek();
            q.push(i);
        }
        //清空单调栈
        q.clear();
        for (int i = n - 1; i >= 0; i--) {
            //从右往左构造单调栈
            while (!q.isEmpty() && heights[q.peek()] >= heights[i]) {
                q.pop();
            }
            right[i] = q.isEmpty() ? n : q.peek();
            q.push(i);
        }
        int ans = 0;
        //求矩形面积
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}
//时间复杂度: O(n)
//空间复杂度: O(n)